﻿using System;

namespace Statistics.Trace
{
    /// <summary>
    ///     通用树形结构
    /// </summary>
    /// <typeparam name="TType"></typeparam>
    /// <typeparam name="TInterface"></typeparam>
    public abstract class TreeNode<TType, TInterface> where TType : TreeNode<TType, TInterface>, TInterface
    {
        private readonly TType _self;

        /// <summary>
        ///     此三个字段构成整棵树
        ///     已知树的构建方式有二：
        ///     1. 用集合的方式实现树，缺点是耗内存，优点是实现起来非常简单。
        ///     2. 用俩个字段的方式实现树，缺点是更耗CPU而且实现比较复杂，优点是内存友好。
        ///     这里采用后者，因为它效率更高。而且实现比较复杂，比较有挑战。
        /// </summary>
        private TType _parent, _firstChild, _nextSibling;

        /// <summary>
        ///     构造函数
        /// </summary>
        protected TreeNode()
        {
            _self = (TType) this;
        }

        /// <summary>
        ///     获取根节点
        /// </summary>
        public TInterface Root
        {
            get
            {
                var root = _self;
                while (root.Parent != null)
                    root = (TType) root.Parent;
                return root;
            }
        }

        /// <summary>
        ///     父节点
        /// </summary>
        /// <exception cref="ApplicationException"></exception>
        public virtual TInterface Parent
        {
            get => _parent;
            set
            {
                var newParent = (TType) value;
                if (_parent == newParent)
                    return;

                var oldParent = _parent;
                if (_self == newParent)
                    throw new ApplicationException("Parent must not be self.");
                if (IsAncestorOf(newParent))
                    throw new ApplicationException("Parent must not be it's child");

                if (oldParent != null)
                {
                    oldParent.RemoveChild(_self);
                    oldParent.OnHierarchyChanged();
                }

                if (newParent != null)
                {
                    newParent.AddChild(_self);
                    newParent.OnHierarchyChanged();
                }
            }
        }

        /// <summary>
        ///     子节点数量
        /// </summary>
        public int ChildCount => GetChildCount();

        /// <summary>
        ///     无父节点则返回-1
        /// </summary>
        public int SiblingIndex
        {
            get => _parent?.GetChildIndex(_self) ?? -1;
            set
            {
                if (_parent == null)
                    return;

                _parent.MoveChildTo(SiblingIndex, value);
                _parent.OnHierarchyChanged();
            }
        }

        /// <summary>
        ///     根据索引获取子节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public TInterface GetChild(int index)
        {
            return GetChildAt(index);
        }

        /// <summary>
        ///     设置为其父节点的第一个子节点
        /// </summary>
        public void SetAsFirstSibling()
        {
            if (_parent?.ChildCount > 0)
                SiblingIndex = 0;
        }

        /// <summary>
        ///     设置为其父节点的最后一个子节点
        /// </summary>
        public void SetAsLastSibling()
        {
            if (_parent == null)
                return;

            var childCount = _parent.ChildCount;
            if (childCount > 0)
                SiblingIndex = childCount - 1;
        }

        /// <summary>
        ///     层级变更事件
        /// </summary>
        protected virtual void OnHierarchyChanged()
        {
        }

        /// <summary>
        ///     是否是其上层节点
        ///     上层节点不包括本身
        /// </summary>
        /// <param name="child"></param>
        /// <returns></returns>
        private bool IsAncestorOf(TType child)
        {
            var ancestor = _self;

            if (child == null || child == ancestor)
                return false;

            var parent = child._parent;
            while (parent != null)
            {
                if (parent == ancestor)
                    return true;
                parent = parent._parent;
            }

            return false;
        }

        /// <summary>
        ///     修改子节点的索引
        /// </summary>
        private void MoveChildTo(int fromIndex, int toIndex)
        {
            var parent = _self;

            var childCount = parent.GetChildCount();
            if (fromIndex < 0 || fromIndex >= childCount
                              || toIndex < 0 || toIndex >= childCount)
                throw new ArgumentOutOfRangeException();
            if (fromIndex == toIndex)
                return;

            var child = (TType) parent.GetChild(fromIndex);
            var childNextSibling = child._nextSibling;

            var forward = fromIndex < toIndex;
            var start = forward ? fromIndex : toIndex;
            ;
            var end = forward ? toIndex : fromIndex;
            var i = 0;
            TType pre = null;
            var cur = parent._firstChild;
            while (cur != null)
            {
                if (forward)
                {
                    // 删除
                    if (i == start)
                    {
                        if (pre == null)
                            parent._firstChild = cur._nextSibling;
                        else
                            pre._nextSibling = cur._nextSibling;
                    }

                    // 插入
                    if (i == end)
                    {
                        child._nextSibling = cur._nextSibling;
                        cur._nextSibling = child;
                        break;
                    }
                }
                else
                {
                    // 插入
                    if (i == start)
                    {
                        child._nextSibling = cur;
                        if (pre == null)
                            parent._firstChild = child;
                        else
                            pre._nextSibling = child;
                    }

                    // 重新连接（删除）
                    if (i == end - 1)
                    {
                        cur._nextSibling = childNextSibling;
                        break;
                    }
                }


                i++;
                pre = cur;
                cur = cur._nextSibling;
            }
        }

        /// <summary>
        ///     获取子节点个数
        /// </summary>
        /// <returns></returns>
        private int GetChildCount()
        {
            var parent = this;

            var count = 0;
            var nextSibling = parent._firstChild;
            while (nextSibling != null)
            {
                count++;
                nextSibling = nextSibling._nextSibling;
            }

            return count;
        }

        /// <summary>
        ///     获取子节点
        /// </summary>
        private TType GetChildAt(int index)
        {
            var parent = this;

            if (index < 0 || index > parent.GetChildCount())
                throw new ArgumentOutOfRangeException();

            var count = 0;
            var nextSibling = parent._firstChild;
            while (nextSibling != null)
            {
                if (count == index)
                    return nextSibling;
                count++;
                nextSibling = nextSibling._nextSibling;
            }

            return null;
        }

        /// <summary>
        ///     获取子节点对应的索引
        /// </summary>
        private int GetChildIndex(TType child)
        {
            var parent = this;

            if (child == null)
                throw new ArgumentNullException();
            if (child._parent != parent)
                throw new ArgumentException("Parent mismatch.");

            var index = 0;
            var nextSibling = parent._firstChild;
            while (nextSibling != null)
            {
                if (child == nextSibling)
                    return index;
                index++;
                nextSibling = nextSibling._nextSibling;
            }

            return -1;
        }

        /// <summary>
        ///     获取前一个兄弟节点
        ///     首节点的前一个兄弟节点为null
        /// </summary>
        private TType GetPrevSibling(TType child)
        {
            var parent = _self;

            if (child == null)
                throw new ArgumentNullException();
            if (child._parent != parent)
                throw new ArgumentException("Parent mismatch.");

            var nextSibling = parent._firstChild;
            while (nextSibling != null)
            {
                if (nextSibling._nextSibling == child)
                    break;
                nextSibling = nextSibling._nextSibling;
            }

            return nextSibling;
        }

        /// <summary>
        ///     获取最后一个子节点
        /// </summary>
        /// <returns></returns>
        private TType GetLastChild()
        {
            var parent = _self;

            var nextSibling = parent._firstChild;
            while (nextSibling != null)
            {
                if (nextSibling._nextSibling == null)
                    break;
                nextSibling = nextSibling._nextSibling;
            }

            return nextSibling;
        }

        /// <summary>
        ///     新增子节点
        /// </summary>
        private void AddChild(TType child)
        {
            var parent = _self;

            if (child == null)
                throw new ArgumentNullException();
            if (child._parent != null || child._nextSibling != null)
                throw new ArgumentException("This child is not isolated.");

            var lastChild = parent.GetLastChild();

            // 首节点
            if (lastChild == null)
                parent._firstChild = child;
            // 添加至末尾
            else
                lastChild._nextSibling = child;

            // 添加至树中
            child._parent = parent;
        }

        /// <summary>
        ///     移除子节点
        /// </summary>
        private void RemoveChild(TType child)
        {
            var parent = _self;

            if (child == null)
                throw new ArgumentNullException();
            if (child._parent != parent)
                throw new ArgumentException("Do not include child.");

            // 首节点
            if (parent._firstChild == child)
            {
                parent._firstChild = child._nextSibling;
            }
            // 重新建立连接
            else
            {
                var prevChild = parent.GetPrevSibling(child);
                prevChild._nextSibling = child._nextSibling;
            }

            // 从树中断开
            child._parent = null;
            child._nextSibling = null;
        }
    }
}